/**
 * 剑指 Offer 33. 二叉搜索树的后序遍历序列
 * https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
 */
public class Solutions_Offer_33 {
    public static void main(String[] args) {
//        int[] postorder = {1, 6, 3, 2, 5};  // output: false
        int[] postorder = {1, 3, 2, 6, 5};  // output: true

        boolean result = verifyPostorder(postorder);
        System.out.println(result);
    }

    public static boolean verifyPostorder(int[] postorder) {
        if (postorder == null || postorder.length < 3) {
            return true;
        }
        return dfs(postorder, 0, postorder.length - 1);
    }

    public static boolean dfs(int[] postorder, int left, int right) {
        if (left >= right) {
            return true;
        }
        // [left, right - 1] 中找到第一个大于 postorder[right] 的元素
        // 中序遍历时，postorder[right] 一定是根节点
        int root = postorder[right];
        int i = 0;
        for (; i < right; i++) {
            if (postorder[i] > root) {
                break;
            }
        }
        // postorder[left, i - 1] 都是小于 root 的元素，即是 root 的左子树
        // postorder[i, right - 1] 都是大于 root 的元素，即是 root 的右子树
        for (int j = i + 1; j < right; j++) {
            // 循环判断，右子树中不可能存在小于 root 的元素
            if (postorder[j] < root) {
                // 不满足条件，return false
                return false;
            }
        }
        // 递归解决子问题，保证左右子树也是一个二叉搜索树
        return dfs(postorder, left, i - 1) && dfs(postorder, i, right - 1);
    }
}
